class Solution {
    public int minimumTotal(List<List<Integer>> triangle) {
        int n = triangle.size();
        int[][] f = new int[2][n];
        f[0&1][0] = triangle.get(0).get(0);
        for (int i = 1; i < n; i++) {
            Arrays.fill(f[i&1], 0);
            f[i&1][0] = f[(i-1)&1][0] + triangle.get(i).get(0);
            for (int j = 1; j < i; j++) {
                f[i&1][j] = Math.min(f[(i-1)&1][j], f[(i-1)&1][j-1]) + triangle.get(i).get(j);
            }
            f[i&1][i] = f[(i-1)&1][i-1] + triangle.get(i).get(i);
        }
        int ans = Integer.MAX_VALUE;
        for (int j = 0; j < n; j++) {
            ans = Math.min(ans, f[(n-1)&1][j]);
        }
        return ans;
    }
}
